Online Judge►LeetCode

[LeetCode] 287 - Find the Duplicate Number

題意

一個 n+1 長度的陣列中含有元素 1~n ，找出重複的那個元素。

解法

利用快慢指針的做法，元素皆指向該索引，找到環的起點即可。

例如：14423
1 -> 4 -> 3 -> 2 -> 4 -> 3 -> 2 -> … 找到重複數 4 即是環的起點

程式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function(nums) {
    
  let slow = nums[0];
  let fast = nums[nums[0]];
  while ( fast !== slow ){
    fast = nums[nums[fast]];
    slow = nums[slow];
    if ( fast === slow ){
      slow = 0;
      while ( slow !== fast ){
        slow = nums[slow];
        fast = nums[fast];
      }
      return slow;
    }
  }
  return slow;
};